{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Step-By-Step Directions From a Binary Tree Node to Another"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getDirections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从二叉树一个节点到另一个节点每一步的方向"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>二叉树</strong>&nbsp;的根节点&nbsp;<code>root</code>&nbsp;，这棵二叉树总共有&nbsp;<code>n</code>&nbsp;个节点。每个节点的值为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;中的一个整数，且互不相同。给你一个整数&nbsp;<code>startValue</code>&nbsp;，表示起点节点 <code>s</code>&nbsp;的值，和另一个不同的整数&nbsp;<code>destValue</code>&nbsp;，表示终点节点&nbsp;<code>t</code>&nbsp;的值。</p>\n",
    "\n",
    "<p>请找到从节点&nbsp;<code>s</code>&nbsp;到节点 <code>t</code>&nbsp;的 <strong>最短路径</strong>&nbsp;，并以字符串的形式返回每一步的方向。每一步用 <strong>大写</strong>&nbsp;字母&nbsp;<code>'L'</code>&nbsp;，<code>'R'</code>&nbsp;和&nbsp;<code>'U'</code>&nbsp;分别表示一种方向：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'L'</code>&nbsp;表示从一个节点前往它的 <strong>左孩子</strong>&nbsp;节点。</li>\n",
    "\t<li><code>'R'</code>&nbsp;表示从一个节点前往它的 <strong>右孩子</strong>&nbsp;节点。</li>\n",
    "\t<li><code>'U'</code>&nbsp;表示从一个节点前往它的 <strong>父</strong>&nbsp;节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回从 <code>s</code>&nbsp;到 <code>t</code>&nbsp;<strong>最短路径</strong>&nbsp;每一步的方向。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/15/eg1.png\" style=\"width: 214px; height: 163px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6\n",
    "<b>输出：</b>\"UURL\"\n",
    "<b>解释：</b>最短路径为：3 → 1 → 5 → 2 → 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/15/eg2.png\" style=\"width: 74px; height: 102px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>root = [2,1], startValue = 2, destValue = 1\n",
    "<b>输出：</b>\"L\"\n",
    "<b>解释：</b>最短路径为：2 → 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目为&nbsp;<code>n</code>&nbsp;。</li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= n</code></li>\n",
    "\t<li>树中所有节点的值 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>\n",
    "\t<li><code>startValue != destValue</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [step-by-step-directions-from-a-binary-tree-node-to-another](https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [step-by-step-directions-from-a-binary-tree-node-to-another](https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,2,3,null,6,4]\\n3\\n6', '[2,1]\\n2\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        ans = \"\"\n",
    "        s_dir, t_dir = \"\", \"\"\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            nonlocal s_dir, t_dir, ans\n",
    "            if ans:\n",
    "                return True, True\n",
    "            # initialize s and t\n",
    "            s, t = False, False\n",
    "            if node.val == startValue:\n",
    "                s = True\n",
    "            if node.val == destValue:\n",
    "                t = True\n",
    "            # base case\n",
    "            if not node.left and not node.right:\n",
    "                return s, t\n",
    "            # recursive case\n",
    "            if node.left:\n",
    "                ls, lt = dfs(node.left)\n",
    "                if ls:\n",
    "                    s = ls\n",
    "                    s_dir += 'U'\n",
    "                if lt:\n",
    "                    t = lt\n",
    "                    t_dir += 'L'\n",
    "            if node.right:\n",
    "                rs, rt = dfs(node.right)\n",
    "                if rs:\n",
    "                    s = rs\n",
    "                    s_dir += 'U'\n",
    "                if rt:\n",
    "                    t = rt\n",
    "                    t_dir += 'R'\n",
    "            if s and t and not ans:\n",
    "                # at the lowest common predecessor\n",
    "                lcp = node\n",
    "                ans = s_dir + t_dir[::-1]\n",
    "            return s, t\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        # find the closest common ancestor\n",
    "        '''\n",
    "        s = []\n",
    "        d = []\n",
    "        ans = \"\"\n",
    "        def inorder(root, direction, path):\n",
    "            nonlocal s, d\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(direction)\n",
    "            if root.val == startValue:\n",
    "                s = path[::]\n",
    "            elif root.val == destValue:\n",
    "                d = path[::]\n",
    "            if s and d:\n",
    "                return\n",
    "            inorder(root.left, \"L\", path)\n",
    "            inorder(root.right, \"R\", path)\n",
    "            path.pop()\n",
    "        inorder(root, \"N\", [])\n",
    "        s = s[1:]\n",
    "        d = d[1:]\n",
    "        minPtr = min(len(s), len(d))\n",
    "        i = 0\n",
    "        while i < minPtr:\n",
    "            if s[i] != d[i]:\n",
    "                break\n",
    "            i += 1\n",
    "        for _ in s[i:]:\n",
    "            ans += \"U\"\n",
    "        return ans + \"\".join(d[i:])\n",
    "        '''\n",
    "        stack = []\n",
    "        ans = \"\"\n",
    "        s = []\n",
    "        d = []\n",
    "        path = []\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                direction = \"L\"\n",
    "                if root.val == startValue:\n",
    "                    s = path[::]\n",
    "                elif root.val == destValue:\n",
    "                    d = path[::]\n",
    "                path.append(direction)\n",
    "                root = root.left\n",
    "            root = stack[-1]\n",
    "            root = root.right\n",
    "            if root != None:\n",
    "                stack[-1].right = None\n",
    "                path.pop()\n",
    "                direction = \"R\"\n",
    "                path.append(direction)\n",
    "                pass\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                # postorder\n",
    "                path.pop()\n",
    "                root = None\n",
    "        minPtr = min(len(s), len(d))\n",
    "        i = 0\n",
    "        while i < minPtr:\n",
    "            if s[i] != d[i]:\n",
    "                break\n",
    "            i += 1\n",
    "        for _ in s[i:]:\n",
    "            ans += \"U\"\n",
    "        return ans + \"\".join(d[i:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        s = [(root, \"\")]\n",
    "        startPath = destPath = None\n",
    "        while s:\n",
    "            node, path = s.pop()\n",
    "            if node.val == startValue:\n",
    "                startPath = path\n",
    "            if node.val == destValue:\n",
    "                destPath = path\n",
    "            if node.left:\n",
    "                s.append((node.left, path + \"L\"))\n",
    "            if node.right:\n",
    "                s.append((node.right, path + \"R\"))\n",
    "            if startPath and destPath:\n",
    "                break\n",
    "        i = 0\n",
    "        n = min(len(startPath), len(destPath))\n",
    "        while i < n and startPath[i] == destPath[i]:\n",
    "            i += 1\n",
    "        return \"U\" * (len(startPath) - i) + destPath[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        s = [root]\n",
    "        path = []\n",
    "        flag = [0]\n",
    "        startPath = destPath = None\n",
    "        while s:\n",
    "            node = s[-1]\n",
    "            if node.val == startValue:\n",
    "                startPath = \"\".join(path)\n",
    "            if node.val == destValue:\n",
    "                destPath = \"\".join(path)\n",
    "            if startPath != None and destPath != None:\n",
    "                break\n",
    "            if node.left:\n",
    "                s.append(node.left)\n",
    "                path.append(\"L\")\n",
    "                flag.append(0)\n",
    "            else:\n",
    "                while not s[-1].right or flag[-1]:\n",
    "                    # print([n.val for n in s], path, startPath, destPath)\n",
    "                    s.pop()\n",
    "                    path.pop()\n",
    "                    flag.pop()\n",
    "                if s:\n",
    "                    flag[-1] = 1\n",
    "                    s.append(s[-1].right)\n",
    "                    path.append(\"R\")\n",
    "                    flag.append(0)\n",
    "        i = 0\n",
    "        n = min(len(startPath), len(destPath))\n",
    "        while i < n and startPath[i] == destPath[i]:\n",
    "            i += 1\n",
    "        return \"U\" * (len(startPath) - i) + destPath[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        n=10**5+1\n",
    "        parent=[0]*n\n",
    "        direction=['']*n\n",
    "        root_val=root.val\n",
    "        q=[root]\n",
    "        n=0\n",
    "        while q:\n",
    "            p=q.pop()\n",
    "            n=max(n,p.val)\n",
    "            if p.left:\n",
    "                parent[p.left.val]=p.val\n",
    "                direction[p.left.val]='L'\n",
    "                q.append(p.left)\n",
    "            if p.right:\n",
    "                parent[p.right.val]=p.val\n",
    "                direction[p.right.val]='R'\n",
    "                q.append(p.right)\n",
    "        parent=parent[:n+1]\n",
    "        direction=direction[:n+1]\n",
    "        for i in range(1,n+1):\n",
    "            pass\n",
    "\n",
    "        def get_up_trace(st):\n",
    "            buf=[]\n",
    "            while st!=root_val:\n",
    "                buf.append('U')\n",
    "                st=parent[st]\n",
    "            return buf\n",
    "\n",
    "        def get_down_trace(st):\n",
    "            buf=[]\n",
    "            while st!=root_val:\n",
    "                buf.append(direction[st])\n",
    "                st=parent[st]\n",
    "            return buf[::-1]\n",
    "        # st -> ed = (up(st) cut common_len(down(st),down(ed)))+ down(ed) cut also\n",
    "        def get_common_len(trace1,trace2):\n",
    "            left,right=0,min(len(trace1),len(trace2))\n",
    "            ans=0\n",
    "            for i in range(right):\n",
    "                if trace1[i]!=trace2[i]:\n",
    "                    break\n",
    "                else:\n",
    "                    ans=i+1\n",
    "            return ans\n",
    "        down_st=get_down_trace(startValue)\n",
    "        down_ed=get_down_trace(destValue)\n",
    "        up_st=get_up_trace(startValue)\n",
    "        common_len=get_common_len(down_st,down_ed)\n",
    "        buf=[*up_st[common_len:],*down_ed[common_len:]]\n",
    "        return ''.join(buf)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        s=[root]\n",
    "        root.u=None\n",
    "        while s:\n",
    "            node=s.pop()\n",
    "            if node.val==startValue: source=node\n",
    "            if node.left:\n",
    "                node.left.u=node\n",
    "                s.append(node.left)\n",
    "            if node.right:\n",
    "                node.right.u=node\n",
    "                s.append(node.right)\n",
    "        vis=set()\n",
    "        q=deque([(source,'')])\n",
    "        while q:\n",
    "            node,path=q.popleft()\n",
    "            vis.add(node.val)\n",
    "            if node.val==destValue:\n",
    "                return path\n",
    "            if node.left and node.left.val not in vis: \n",
    "                    q.append((node.left,path+'L'))\n",
    "            if node.right and node.right.val not in vis: \n",
    "                q.append((node.right,path+'R'))\n",
    "            if node.u and node.u.val not in vis: \n",
    "                q.append((node.u,path+'U'))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        dct = [dict()]\n",
    "        stack = [root]\n",
    "        n = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            n += 1\n",
    "            if node.left:\n",
    "                a, b = node.val, node.left.val\n",
    "                while len(dct) < a+1 or len(dct) < b+1:\n",
    "                    dct.append(dict())\n",
    "\n",
    "                dct[node.val - 1][node.left.val - 1] = \"L\"\n",
    "                dct[node.left.val - 1][node.val - 1] = \"U\"\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                a, b = node.val, node.right.val\n",
    "                while len(dct) < a+1 or len(dct) < b+1:\n",
    "                    dct.append(dict())\n",
    "                dct[node.val - 1][node.right.val - 1] = \"R\"\n",
    "                dct[node.right.val - 1][node.val - 1] = \"U\"\n",
    "                stack.append(node.right)\n",
    "\n",
    "        stack = [[destValue - 1, -1]]\n",
    "        parent = [-1] * n\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            for j in dct[i]:\n",
    "                if j != fa:\n",
    "                    parent[j] = i\n",
    "                    stack.append([j, i])\n",
    " \n",
    "        ans = \"\"\n",
    "        node = startValue - 1\n",
    "        while node != destValue - 1:\n",
    "            ans += dct[node][parent[node]]\n",
    "            node = parent[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        graph = collections.defaultdict(list)\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.left:\n",
    "                graph[node.left.val].append((node.val, 'U'))\n",
    "                graph[node.val].append((node.left.val, 'L'))\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                graph[node.right.val].append((node.val, 'U'))\n",
    "                graph[node.val].append((node.right.val, 'R'))\n",
    "                queue.append(node.right)\n",
    "        queue.append((startValue, ''))\n",
    "        #queue = collections.deque([(startValue, '')])\n",
    "        seen = set()\n",
    "        while queue:\n",
    "            cur_val, cur_path = queue.popleft()\n",
    "            if cur_val in seen:\n",
    "                continue\n",
    "            seen.add(cur_val)\n",
    "            if cur_val == destValue:\n",
    "                return cur_path\n",
    "            else:\n",
    "                for child, direction in graph[cur_val]:\n",
    "                    if child not in seen:\n",
    "                        queue.append((child, cur_path+direction))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        graph = collections.defaultdict(list)\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.left:\n",
    "                graph[node.val].append([node.left.val, \"L\"])\n",
    "                graph[node.left.val].append([node.val, \"U\"]) \n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                graph[node.val].append([node.right.val, \"R\"])\n",
    "                graph[node.right.val].append([node.val, \"U\"]) \n",
    "                queue.append(node.right)\n",
    "\n",
    "        queue = collections.deque()\n",
    "        queue.append([startValue, \"\"])\n",
    "        visited = set() # NameError: name 'visited' is not defined\n",
    "        visited.add(startValue)\n",
    "    \n",
    "        while queue:\n",
    "            node, steps = queue.popleft()\n",
    "            if node == destValue:\n",
    "                return steps\n",
    "            for nei, step in graph[node]:\n",
    "                if nei not in visited:\n",
    "                    queue.append([nei, steps + step])\n",
    "                    visited.add(nei)\n",
    "        return \"\"\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root1: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        hashmap=defaultdict(list)\n",
    "        q=deque([root1])\n",
    "        def dfs(root):\n",
    "            if root.left:\n",
    "                hashmap[root.val].append((root.left.val,\"L\"))\n",
    "                hashmap[root.left.val].append((root.val,\"U\"))\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                hashmap[root.val].append((root.right.val,\"R\"))\n",
    "                hashmap[root.right.val].append((root.val,\"U\"))\n",
    "                dfs(root.right)\n",
    "        while q:\n",
    "            root=q.popleft()\n",
    "            if root.left:\n",
    "                q.append(root.left)\n",
    "                hashmap[root.val].append((root.left.val,\"L\"))\n",
    "                hashmap[root.left.val].append((root.val,\"U\"))\n",
    "            if root.right:\n",
    "                q.append(root.right)\n",
    "                hashmap[root.val].append((root.right.val,\"R\"))\n",
    "                hashmap[root.right.val].append((root.val,\"U\"))\n",
    "\n",
    "        q1=deque([(startValue,\"\")])\n",
    "        vis={startValue}\n",
    "        while q1:\n",
    "            node,path=q1.popleft()\n",
    "            if node==destValue:\n",
    "                return path\n",
    "            for nextt_node,next_statu in hashmap[node]:\n",
    "                if nextt_node not in vis:\n",
    "                    q1.append((nextt_node,path+next_statu))\n",
    "                    vis.add(nextt_node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        dct = defaultdict(dict)\n",
    "        stack = [root]\n",
    "        n = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            n += 1\n",
    "            if node.left:\n",
    "                dct[node.val - 1][node.left.val - 1] = \"L\"\n",
    "                dct[node.left.val - 1][node.val - 1] = \"U\"\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                dct[node.val - 1][node.right.val - 1] = \"R\"\n",
    "                dct[node.right.val - 1][node.val - 1] = \"U\"\n",
    "                stack.append(node.right)\n",
    "\n",
    "        stack = [[destValue - 1, -1]]\n",
    "        parent = [-1] * n\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            for j in dct[i]:\n",
    "                if j != fa:\n",
    "                    parent[j] = i\n",
    "                    stack.append([j, i])\n",
    " \n",
    "        ans = \"\"\n",
    "        node = startValue - 1\n",
    "        while node != destValue - 1:\n",
    "            ans += dct[node][parent[node]]\n",
    "            node = parent[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root, startValue: int, destValue: int) -> str:\n",
    "        dirs = {}\n",
    "        g = defaultdict(list)\n",
    "        Q = deque()\n",
    "        Q.append(root)\n",
    "        vals = []\n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            vals.append(u.val)\n",
    "            if u.left:\n",
    "                left = u.left\n",
    "                dirs[(u.val, left.val)] = 'L'\n",
    "                dirs[(left.val, u.val)] = 'U'\n",
    "                g[u.val].append(left.val)\n",
    "                g[left.val].append(u.val)\n",
    "                Q.append(left)\n",
    "            if u.right:\n",
    "                right = u.right\n",
    "                dirs[(u.val, right.val)] = 'R'\n",
    "                dirs[(right.val, u.val)] = 'U'\n",
    "                g[u.val].append(right.val)\n",
    "                g[right.val].append(u.val)\n",
    "                Q.append(right)\n",
    "        path = []\n",
    "        Q = deque()\n",
    "        Q.append(startValue)\n",
    "        vis = set()\n",
    "        vis.add(startValue)\n",
    "        n = max(vals)\n",
    "        pre = [-1] * (n+1)\n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            path.append(u)\n",
    "            if u == destValue:\n",
    "                break\n",
    "            for v in g[u]:\n",
    "                if v not in vis:\n",
    "                    pre[v] = u\n",
    "                    Q.append(v)\n",
    "                    vis.add(v)\n",
    "        cur = pre[destValue]\n",
    "        path = [destValue]\n",
    "        while cur != -1:\n",
    "            path.append(cur)\n",
    "            cur = pre[cur]\n",
    "        path = path[::-1]\n",
    "        s = ''\n",
    "        for i in range(len(path) - 1):\n",
    "            s += dirs[(path[i], path[i + 1])]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        startNode, destNode = self.findTarget(root, startValue, destValue)\n",
    "        startPath, startVals = self.findPath(startNode)\n",
    "        destPath, destVals = self.findPath(destNode)\n",
    "        print(startPath, startVals, destPath, destVals )\n",
    "        i = len(startVals)-1\n",
    "        j = len(destVals)-1\n",
    "        while (i >= 0 and j >= 0 and startVals[i] == destVals[j]):\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        if j < 0:\n",
    "            return \"U\"*(i+1)\n",
    "        else :\n",
    "            return \"U\"*(i+1) + str(destPath[j::-1])\n",
    "\n",
    "\n",
    "    def findTarget(self, root, startValue, destValue):\n",
    "        root.direction = None\n",
    "        root.parent = None\n",
    "        res = [root, root]\n",
    "        i = 0\n",
    "        stack = [root]\n",
    "        while i<2:\n",
    "            cur = stack.pop()\n",
    "            if cur.val == startValue:\n",
    "                res[0] = cur\n",
    "                i += 1\n",
    "            if cur.val == destValue:\n",
    "                res[1] = cur\n",
    "                i += 1\n",
    "            if cur.left is not None:\n",
    "                stack.append(cur.left)\n",
    "                cur.left.parent = cur\n",
    "                cur.left.direction = \"L\"\n",
    "            if cur.right is not None:\n",
    "                stack.append(cur.right)\n",
    "                cur.right.parent = cur\n",
    "                cur.right.direction = \"R\"\n",
    "        return res\n",
    "\n",
    "    def findPath(self, node):\n",
    "        path = ''\n",
    "        vals = []\n",
    "        cur = node\n",
    "        while (cur.parent is not None):\n",
    "            path += cur.direction\n",
    "            vals.append(cur.val)\n",
    "            cur = cur.parent\n",
    "        vals.append(cur.val)\n",
    "        return [path, vals]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], s: int, d: int) -> str:\n",
    "        \n",
    "        # 找到公共祖先\n",
    "        def dfs(root, p, q):\n",
    "            if not root or root.val == p or root.val == q: return root\n",
    "            left = dfs(root.left, p, q)\n",
    "            right = dfs(root.right, p, q)\n",
    "            if not left: return right\n",
    "            if not right: return left\n",
    "            return root\n",
    "        \n",
    "        anc=dfs(root,s,d)\n",
    "        target=anc.val\n",
    "        # print(target)\n",
    "        # 从根节点记录每个点和下一个点的关系\n",
    "        g=defaultdict(lambda:defaultdict(lambda:None))\n",
    "        parent={}\n",
    "        q=collections.deque()\n",
    "        q.append(anc)\n",
    "        while q:\n",
    "            root=q.popleft()\n",
    "            if root.left:\n",
    "                g[root.val][root.left.val]='L'\n",
    "                g[root.left.val][root.val]='U'\n",
    "                q.append(root.left)\n",
    "                parent[root.left.val]=root.val\n",
    "            if root.right:\n",
    "                g[root.val][root.right.val]='R'\n",
    "                g[root.right.val][root.val]='U'\n",
    "                q.append(root.right)\n",
    "                parent[root.right.val]=root.val\n",
    "        \n",
    "        # 找到路径\n",
    "        res=\"\"\n",
    "        pre=None\n",
    "        while True:\n",
    "            if s == target:\n",
    "                break\n",
    "            res+='U'\n",
    "            s=parent[s]\n",
    "        \n",
    "        res1=\"\"\n",
    "        while True:\n",
    "            if d == target:\n",
    "                break\n",
    "            res1+=g[parent[d]][d]\n",
    "            d=parent[d]\n",
    "            \n",
    "        return res+res1[::-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import *\n",
    " \n",
    "def dijkstra_raw(edges, from_node, to_node):\n",
    "\tg = defaultdict(list)\n",
    "\tfor l,r,c in edges:\n",
    "\t\tg[l].append((c,r))\n",
    "\tq, seen = [(0,from_node,())], set()\n",
    "\twhile q:\n",
    "\t\t(cost,v1,path) = heappop(q)\n",
    "\t\tif v1 not in seen:\n",
    "\t\t\tseen.add(v1)\n",
    "\t\t\tpath = (v1, path)\n",
    "\t\t\tif v1 == to_node:\n",
    "\t\t\t\treturn cost,path\n",
    "\t\t\tfor c, v2 in g.get(v1, ()):\n",
    "\t\t\t\tif v2 not in seen:\n",
    "\t\t\t\t\theappush(q, (cost+c, v2, path))\n",
    "\treturn float(\"inf\"),[]\n",
    " \n",
    "def dijkstra(edges, from_node, to_node):\n",
    "\tlen_shortest_path = -1\n",
    "\tret_path=[]\n",
    "\tlength,path_queue = dijkstra_raw(edges, from_node, to_node)\n",
    "\tif len(path_queue)>0:\n",
    "\t\tlen_shortest_path = length\t\t## 1. Get the length firstly;\n",
    "\t\t## 2. Decompose the path_queue, to get the passing nodes in the shortest path.\n",
    "\t\tleft = path_queue[0]\n",
    "\t\tret_path.append(left)\t\t## 2.1 Record the destination node firstly;\n",
    "\t\tright = path_queue[1]\n",
    "\t\twhile len(right)>0:\n",
    "\t\t\tleft = right[0]\n",
    "\t\t\tret_path.append(left)\t## 2.2 Record other nodes, till the source-node.\n",
    "\t\t\tright = right[1]\n",
    "\t\tret_path.reverse()\t## 3. Reverse the list finally, to make it be normal sequence.\n",
    "\treturn len_shortest_path,ret_path\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        edges = []\n",
    "        edge2dir = {}\n",
    "        q = []\n",
    "        q.append(root)\n",
    "        while len(q) > 0:\n",
    "            node = q.pop(0)\n",
    "            if node.left:\n",
    "                edges.append((node.val, node.left.val, 1))\n",
    "                edges.append((node.left.val, node.val, 1))\n",
    "                edge2dir[(node.val, node.left.val)] = 'L'\n",
    "                edge2dir[(node.left.val, node.val)] = 'U'\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                edges.append((node.val, node.right.val, 1))\n",
    "                edges.append((node.right.val, node.val, 1))\n",
    "                edge2dir[(node.val, node.right.val)] = 'R'\n",
    "                edge2dir[(node.right.val, node.val)] = 'U'\n",
    "                q.append(node.right)\n",
    "                \n",
    "        _, path = dijkstra(edges, startValue, destValue)\n",
    "        res = []\n",
    "        for i in range(1, len(path)):\n",
    "            res.append(edge2dir[(path[i-1], path[i])])\n",
    "        # print(res)\n",
    "        res = ''.join(res)\n",
    "        return res\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:        \n",
    "        path_A = findPath(root, startValue, [])\n",
    "        path_B = findPath(root, destValue, [])\n",
    "        i = 0\n",
    "        while i<min(len(path_A), len(path_B)):\n",
    "            if path_A[i] != path_B[i]:\n",
    "                break\n",
    "            i += 1\n",
    "        return \"\".join(['U']*(len(path_A)-i)+path_B[i:])\n",
    "\n",
    "def findPath(root, val, path):\n",
    "    if root is None:\n",
    "        return None\n",
    "    elif root.val == val:\n",
    "        return path\n",
    "    \n",
    "    path.append(\"L\")\n",
    "    ans = findPath(root.left, val, path)\n",
    "    if ans: return ans\n",
    "    path.pop()\n",
    "    \n",
    "    path.append(\"R\")\n",
    "    ans = findPath(root.right, val, path)\n",
    "    if ans: return ans\n",
    "    path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        self.path1, self.path2, self.tar1, self.tar2 = [], [], startValue, destValue\n",
    "        self.flag = 0\n",
    "        self.dfs(root, [],)\n",
    "        m, n = len(self.path1), len(self.path2)\n",
    "        i, k = 0, min(m, n)\n",
    "        while i < k and self.path1[i] == self.path2[i]: i += 1\n",
    "        return \"\".join([\"U\"] * (m-i) + self.path2[i:])\n",
    "    def dfs(self, root, path,):\n",
    "        if not root: return\n",
    "        if root.val == self.tar1:\n",
    "            self.path1 = path.copy()\n",
    "            self.flag += 1\n",
    "        if root.val == self.tar2:\n",
    "            self.path2 = path.copy()\n",
    "            self.flag += 1\n",
    "        if self.flag == 2: return\n",
    "        path.append('L')\n",
    "        self.dfs(root.left, path)\n",
    "        path[-1] = 'R'\n",
    "        self.dfs(root.right, path)\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findNode(self, node, value, path):\n",
    "        if not node:\n",
    "            return False\n",
    "        if node.val == value:\n",
    "            return True\n",
    "        path.append(\"L\")\n",
    "        if self.findNode(node.left, value, path):\n",
    "            return True\n",
    "        path.pop()\n",
    "        path.append(\"R\")\n",
    "        if self.findNode(node.right, value, path):\n",
    "            return True\n",
    "        path.pop()\n",
    "        \n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        pathStart = []\n",
    "        pathDest = []\n",
    "        self.findNode(root, startValue, pathStart)\n",
    "        self.findNode(root, destValue, pathDest)\n",
    "        sameCount = 0\n",
    "        while sameCount < len(pathStart) and sameCount < len(pathDest):\n",
    "            if pathStart[sameCount] == pathDest[sameCount]:\n",
    "                sameCount += 1\n",
    "            else:\n",
    "                break\n",
    "        ans = \"U\" * (len(pathStart) - sameCount) + \"\".join(pathDest[sameCount:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right \n",
    "class Solution:\n",
    "    def getDirections(self, root, startValue, destValue):\n",
    "        self.parents = {}\n",
    "        self.dfs(root,None)\n",
    "        start_path = self.getPath(root,startValue)        \n",
    "        dest_path = self.getPath(root,destValue)\n",
    "        if not start_path:\n",
    "            return dest_path\n",
    "        if not dest_path:\n",
    "            return self.getContrary(start_path)\n",
    "        return self.getDir(start_path,dest_path)\n",
    "\n",
    "    def getPath(self,root,cur):\n",
    "        res = ''\n",
    "        while cur != root.val:\n",
    "            parent = self.parents[cur]\n",
    "            res += 'L' if parent.left and parent.left.val == cur else 'R'\n",
    "            cur = parent.val\n",
    "        return res[::-1]\n",
    "\n",
    "    def dfs(self,root, pre):\n",
    "        if not root: return\n",
    "        self.parents[root.val] = pre\n",
    "        self.dfs(root.left, root)\n",
    "        self.dfs(root.right, root)\n",
    "\n",
    "    def getContrary(self, path):\n",
    "        return 'U' * len(path)\n",
    "\n",
    "    def getDir(self,start_path,dest_path):\n",
    "        i = 0\n",
    "        while i<len(start_path) and i<len(dest_path) and start_path[i] == dest_path[i]:\n",
    "            i += 1\n",
    "        if i == len(start_path):\n",
    "            return dest_path[i:]\n",
    "        if i == len(start_path):\n",
    "            return self.getContrary(start_path[i:])\n",
    "        else:\n",
    "            return self.getContrary(start_path[i:]) + dest_path[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        self.startValue = startValue;\n",
    "        self.destValue = destValue;\n",
    "        self.path, self.startPath, self.destPath = [], \"\", \"\";\n",
    "\n",
    "        # 寻找走到 startValue 和 destValue 的方向路径\n",
    "        self.traverse(root);\n",
    "        \n",
    "        # 去除两个方向路径的公共前缀\n",
    "        p = 0; m = len(self.startPath); n = len(self.destPath);\n",
    "        while (p < m and p < n\n",
    "                and self.startPath[p] == self.destPath[p]):\n",
    "            p += 1;\n",
    "\n",
    "        self.startPath = self.startPath[p:];\n",
    "        self.destPath = self.destPath[p:];\n",
    "        # 将走向 startValue 的方向路径全部变成 U\n",
    "        self.startPath = \"U\" * len(self.startPath);\n",
    "        # 组合 startPath 和 destPath 就得到了答案\n",
    "        return self.startPath + self.destPath;\n",
    "\n",
    "\n",
    "    # str.join(), \n",
    "    # 二叉树遍历函数\n",
    "    def traverse(self, root):\n",
    "        if (root is None):\n",
    "            return;\n",
    "        if (root.val == self.startValue):\n",
    "            self.startPath = \"\".join(self.path)\n",
    "        elif (root.val == self.destValue):\n",
    "            self.destPath = \"\".join(self.path)\n",
    "\n",
    "        # 二叉树遍历框架\n",
    "        self.path.append('L');\n",
    "        self.traverse(root.left);\n",
    "        self.path.pop();\n",
    "\n",
    "        self.path.append('R');\n",
    "        self.traverse(root.right);\n",
    "        self.path.pop();\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def _find_path(root: TreeNode, dst: int, path: bytearray) -> bool:\n",
    "    \"\"\"找从root->tn.val==dst的路径.\"\"\"\n",
    "    if root.val == dst:\n",
    "        return True\n",
    "    if root.left is not None and _find_path(root.left, dst, path):\n",
    "        path.append(ord(\"L\"))\n",
    "        return True\n",
    "    if root.right is not None and _find_path(root.right, dst, path):\n",
    "        path.append(ord(\"R\"))\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "\n",
    "def find_path(root: TreeNode, dst: int, path: bytearray) -> None:\n",
    "    _find_path(root, dst, path)\n",
    "    path.reverse()\n",
    "\n",
    "def find_common_ancestor(root: Optional[TreeNode], tn_c: Set[int]) -> Optional[TreeNode]:\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.val in tn_c:\n",
    "        return root\n",
    "    ca_l = find_common_ancestor(root.left, tn_c)  # common ancestor left\n",
    "    ca_r = find_common_ancestor(root.right, tn_c)\n",
    "    # 分类讨论\n",
    "    if ca_r is None:\n",
    "        return ca_l\n",
    "    elif ca_l is None:\n",
    "        return ca_r\n",
    "    else:\n",
    "        return root\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root: TreeNode,\n",
    "                      startValue: int, destValue: int) -> str:\n",
    "        root = find_common_ancestor(root, {startValue, destValue})\n",
    "        path2s = bytearray()\n",
    "        path2d = bytearray()\n",
    "        find_path(root, startValue, path2s)\n",
    "        find_path(root, destValue, path2d)\n",
    "        res = bytearray(b\"U\")\n",
    "        res *= len(path2s)\n",
    "        res += path2d\n",
    "        return res.decode()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # # 最近公共祖先\n",
    "    # https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/solutions/1139430/bfs-zuo-fa-by-endlesscheng-dfcf/\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        path = []\n",
    "    \n",
    "        def dfs(node, target):\n",
    "            nonlocal path\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == target:\n",
    "                return True\n",
    "            path.append('L')\n",
    "            if dfs(node.left, target):\n",
    "                return True\n",
    "            path[-1] = 'R'\n",
    "            if dfs(node.right, target):\n",
    "                return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        \n",
    "        dfs(root, startValue)\n",
    "        pathToStart = list(path)\n",
    "        \n",
    "        path.clear()\n",
    "        dfs(root, destValue)\n",
    "        pathToDest = list(path)\n",
    "        \n",
    "        while pathToStart and pathToDest and pathToStart[0] == pathToDest[0]:\n",
    "            pathToStart.pop(0)\n",
    "            pathToDest.pop(0)\n",
    "        \n",
    "        return 'U' * len(pathToStart) + ''.join(pathToDest)\n",
    "\n",
    "\n",
    "\n",
    "    # dfs\n",
    "    def getDirections2(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        fa = {}   # 父节点哈希表\n",
    "        s = None   # 起点节点\n",
    "        t = None   # 终点节点\n",
    "\n",
    "        # 深度优先搜索维护哈希表与起点终点\n",
    "        def dfs(curr: TreeNode) -> None:\n",
    "            nonlocal s, t\n",
    "            if curr.val == startValue:\n",
    "                s = curr\n",
    "\n",
    "            if curr.val == destValue:\n",
    "                t = curr\n",
    "\n",
    "            if curr.left:\n",
    "                fa[curr.left] = curr\n",
    "                dfs(curr.left)\n",
    "                \n",
    "            if curr.right:\n",
    "                fa[curr.right] = curr\n",
    "                dfs(curr.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        # 求出根节点到对应节点的路径字符串\n",
    "        def path(curr: TreeNode) -> List[str]:\n",
    "            res = []\n",
    "            while curr != root:\n",
    "                par = fa[curr]\n",
    "                if curr == par.left:\n",
    "                    res.append('L')\n",
    "                else:\n",
    "                    res.append('R')\n",
    "                    \n",
    "                curr = par\n",
    "\n",
    "            return res[::-1]\n",
    "        \n",
    "        path1 = path(s)\n",
    "        path2 = path(t)\n",
    "        # 计算最长公共前缀并删去对应部分，同时将 path_1 逐字符修改为 'U'\n",
    "        l1, l2 = len(path1), len(path2)\n",
    "        i = 0\n",
    "        while i < min(l1, l2):\n",
    "            if path1[i] == path2[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        finalpath = 'U' * (l1 - i) + ''.join(path2[i:])   # 最短路径对应字符串 \n",
    "        return finalpath\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def LCA(self, root: Optional[TreeNode], p: int, q: int) -> Optional[TreeNode]:\n",
    "        if not root: return None\n",
    "        if root.val == p or root.val == q:\n",
    "            return root\n",
    "        l = self.LCA(root.left, p, q)\n",
    "        r = self.LCA(root.right, p, q)\n",
    "        if l and r: return root\n",
    "        return l if l else r\n",
    "\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        lca = self.LCA(root, startValue, destValue)\n",
    "        v1 = v2 = ''\n",
    "        def dfs1(root, target, step):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val == target:\n",
    "                nonlocal v1\n",
    "                v1 = step * 'U'\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs1(root.left, target, step+1)\n",
    "            if root.right:\n",
    "                dfs1(root.right, target, step+1)\n",
    "        def dfs2(root, target, path):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == target:\n",
    "                nonlocal v2\n",
    "                v2 = ''.join(path)\n",
    "                return\n",
    "            if root.left:\n",
    "                path.append('L')\n",
    "                dfs2(root.left,target,path)\n",
    "                path.pop()\n",
    "            if root.right:\n",
    "                path.append('R')\n",
    "                dfs2(root.right,target,path)\n",
    "                path.pop()\n",
    "        dfs1(lca, startValue, 0)\n",
    "        dfs2(lca, destValue, [])\n",
    "        return v1+v2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从二叉树一个节点到另一个节点每一步的方向，输入：root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6，输出：\"UURL\"\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        start,end=[],[]\n",
    "        def dfs(node):\n",
    "            if not node:return 0\n",
    "            val = 0\n",
    "            if node.val == startValue:val += 1\n",
    "            elif node.val == destValue:val += 2\n",
    "            # 核心算法步骤\n",
    "            # 调用左右子树, 若子树仅有start则添加'U'返回上一层, 若仅有end则添加左右子树对于的tag, 否则什么也不做\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if l == 1:start.append('U')\n",
    "            elif l == 2:end.append('L')\n",
    "            if r == 1:start.append('U')\n",
    "            elif r == 2:end.append('R')\n",
    "            # 对左右子树状态和当前节点状态进行或操作, 返回当前子树状态\n",
    "            return l | r | val\n",
    "        dfs(root)\n",
    "        # 由于添加路径时是顺序时自底向上, 所以end序列需要reverse操作\n",
    "        return ''.join(start + end[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        start = []\n",
    "        end = []\n",
    "        def dfs(node):\n",
    "            \"\"\"返回值状态含义  0: 无, 1:only has start, 2: only has end, 3: has both start and end \"\"\"\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            # 计算当前节点状态\n",
    "            val = 0\n",
    "            if node.val == startValue:\n",
    "                val += 1\n",
    "            elif node.val == destValue:\n",
    "                val += 2\n",
    "\n",
    "            # 核心算法步骤\n",
    "            # 调用左右子树, 若子树仅有start则添加'U'返回上一层, 若仅有end则添加左右子树对于的tag, 否则什么也不做\n",
    "            d = {'L': dfs(node.left), 'R': dfs(node.right)}\n",
    "            for tag, val_sub in d.items():\n",
    "                if val_sub == 1:\n",
    "                    start.append('U')\n",
    "                elif val_sub == 2:\n",
    "                    end.append(tag)\n",
    "            \n",
    "            #等价于对左右子树状态和当前节点状态进行或操作\n",
    "            return sum(d.values(), val)\n",
    "        \n",
    "        dfs(root)\n",
    "        # 由于添加路径时是顺序时自底向上, 所以end序列需要reverse操作\n",
    "        return ''.join(start + end[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        ans = ''\n",
    "        fadict = {}\n",
    "        def dfs(now, fa):\n",
    "            fadict[now.val] = fa\n",
    "            if now.left != None:\n",
    "                dfs(now.left, now)\n",
    "            if now.right != None:\n",
    "                dfs(now.right, now)\n",
    "        dfs(root, root)\n",
    "        nodenum = len(fadict)\n",
    "        nowval = startValue\n",
    "        vis = [0 for _ in range(nodenum+1)]\n",
    "        cnt = 1\n",
    "        while nowval != root.val:\n",
    "            vis[nowval] = cnt\n",
    "            cnt += 1\n",
    "            nowval = fadict[nowval].val\n",
    "        vis[root.val] = cnt\n",
    "        cnt += 1\n",
    "\n",
    "        downstr = ''\n",
    "        upstr = ''\n",
    "        nowval = destValue\n",
    "        while vis[nowval] == 0:\n",
    "            fanode = fadict[nowval]\n",
    "            if fanode.left != None and fanode.left.val == nowval:\n",
    "                downstr += 'L'\n",
    "            elif fanode.right != None and fanode.right.val == nowval:\n",
    "                downstr += 'R'\n",
    "            nowval = fadict[nowval].val\n",
    "        downstr = downstr[::-1]\n",
    "        for i in range(vis[nowval]-1):\n",
    "            upstr += 'U'\n",
    "        return upstr+downstr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        fa = {}   # 父节点哈希表\n",
    "        s = None   # 起点节点\n",
    "        t = None   # 终点节点\n",
    "\n",
    "        # 深度优先搜索维护哈希表与起点终点\n",
    "        def dfs(curr: TreeNode) -> None:\n",
    "            nonlocal s, t\n",
    "            if curr.val == startValue:\n",
    "                s = curr\n",
    "            if curr.val == destValue:\n",
    "                t = curr\n",
    "            if curr.left:\n",
    "                fa[curr.left] = curr\n",
    "                dfs(curr.left)\n",
    "            if curr.right:\n",
    "                fa[curr.right] = curr\n",
    "                dfs(curr.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        # 求出根节点到对应节点的路径字符串\n",
    "        def path(curr: TreeNode) -> List[str]:\n",
    "            res = []\n",
    "            while curr != root:\n",
    "                par = fa[curr]\n",
    "                if curr == par.left:\n",
    "                    res.append('L')\n",
    "                else:\n",
    "                    res.append('R')\n",
    "                curr = par\n",
    "            return res[::-1]\n",
    "        \n",
    "        path1 = path(s)\n",
    "        path2 = path(t)\n",
    "        # 计算最长公共前缀并删去对应部分，同时将 path_1 逐字符修改为 'U'\n",
    "        l1, l2 = len(path1), len(path2)\n",
    "        i = 0\n",
    "        while i < min(l1, l2):\n",
    "            if path1[i] == path2[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        finalpath = 'U' * (l1 - i) + ''.join(path2[i:])   # 最短路径对应字符串 \n",
    "        return finalpath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        d=defaultdict()\n",
    "        start=dest=root\n",
    "        q=deque()\n",
    "        vis=set()\n",
    "        def dfs(cur,fa):\n",
    "            if cur==None:\n",
    "                return \n",
    "            d[cur]=fa\n",
    "            if cur.val==startValue:\n",
    "                q.append([cur,\"\"])\n",
    "                vis.add(cur)\n",
    "            if cur.val==destValue:\n",
    "                dest=cur\n",
    "            dfs(cur.left,cur)\n",
    "            dfs(cur.right,cur)\n",
    "        dfs(root,root)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                node,temp=q.popleft()\n",
    "                if node.val==destValue:\n",
    "                    return temp\n",
    "                if d[node] not in vis:\n",
    "                    q.append([d[node],temp+\"U\"])\n",
    "                    vis.add(d[node])\n",
    "                if node.left!=None and node.left not in vis:\n",
    "                    q.append([node.left,temp+\"L\"])\n",
    "                    vis.add(node.left)\n",
    "                if node.right!=None and node.right not in vis:\n",
    "                    q.append([node.right,temp+\"R\"])\n",
    "                    vis.add(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        path = []\n",
    "        def find(node, val):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == val:\n",
    "                return True\n",
    "            path.append((node.val,\"L\"))\n",
    "            if find(node.left, val):\n",
    "                return True\n",
    "            path.pop()\n",
    "            path.append((node.val,\"R\"))\n",
    "            if not find(node.right, val):\n",
    "                path.pop()\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        find(root, startValue)\n",
    "        path_s = list(path)\n",
    "        print(path_s)\n",
    "        path = []\n",
    "        find(root, destValue)\n",
    "        print(path)\n",
    "        i = 0\n",
    "        while i < len(path_s) and i < len(path) and path_s[i] == path[i]:\n",
    "            i += 1\n",
    "        print(i)\n",
    "        return \"U\" * (len(path_s) - i) + \"\".join(list(zip(*path))[1][i:]) if path else \"U\" * len(path_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        father_dict = {}\n",
    "\n",
    "        def dfs(node, father, left):\n",
    "            if node is not None:\n",
    "                dfs(node.left, node.val, 'L')\n",
    "                father_dict[node.val] = (father, left)\n",
    "                dfs(node.right, node.val, 'R')\n",
    "        dfs(root, -1, None)\n",
    "\n",
    "        sfathers, value = [startValue], startValue\n",
    "        while father_dict[value][0] is not -1:\n",
    "            value = father_dict[value][0]\n",
    "            sfathers.append(value)\n",
    "\n",
    "        dpaths, value = [], destValue\n",
    "        while True:\n",
    "            if value in sfathers:\n",
    "                for i, x in enumerate(sfathers):\n",
    "                    if x == value:\n",
    "                        # print(i, dpaths[::-1])\n",
    "                        return 'U' * i + ''.join(dpaths[::-1])\n",
    "            else:\n",
    "                dpaths.append(father_dict[value][1])\n",
    "                value = father_dict[value][0]\n",
    "\n",
    "\n",
    "\n",
    "        return 'TEST'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        fa = {}\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            if root.left:\n",
    "                fa[root.left.val] = (root.val, 'L')\n",
    "            if root.right:\n",
    "                fa[root.right.val] = (root.val, 'R')\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        # print(fa)\n",
    "        def path(o: int) -> str:\n",
    "            if o not in fa:\n",
    "                return ''\n",
    "            o_fa, d = fa[o]\n",
    "            s = path(o_fa)\n",
    "            return d + s\n",
    "        path1 = path(startValue)[::-1]\n",
    "        path2 = path(destValue)[::-1]\n",
    "        # print(path1, path2)\n",
    "\n",
    "        i = 0\n",
    "        limit = min(len(path1), len(path2))\n",
    "        while i < limit and path1[i] == path2[i]:\n",
    "            i += 1\n",
    "        path1 = path1[i:] if path1 else ''\n",
    "        path2 = path2[i:] if path2 else ''\n",
    "\n",
    "        return 'U' * len(path1) + path2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        def dfs_search(r):\n",
    "            nonlocal common\n",
    "            ans = 0\n",
    "\n",
    "            if r.val == startValue or r.val == destValue:\n",
    "                ans += 1\n",
    "\n",
    "            if r.left:\n",
    "                parent[r.left.val] = (r.val, 0)\n",
    "                ans += dfs_search(r.left)\n",
    "\n",
    "            if r.right:\n",
    "                parent[r.right.val] = (r.val, 1)\n",
    "                ans += dfs_search(r.right)\n",
    "\n",
    "            if not common and ans == 2:\n",
    "                common = r.val\n",
    "\n",
    "            return ans\n",
    "\n",
    "        common = None\n",
    "        parent = dict()\n",
    "        dfs_search(root)\n",
    "        # print(common)\n",
    "        # print(parent)\n",
    "\n",
    "        left = ''\n",
    "        p = startValue\n",
    "        while p != common:\n",
    "            left += 'U'\n",
    "            p, f = parent.get(p)\n",
    "\n",
    "        right = ''\n",
    "        p = destValue\n",
    "        while p != common:\n",
    "            p, f = parent.get(p)\n",
    "            if f == 0:\n",
    "                right = 'L' + right\n",
    "            else:\n",
    "                right = 'R' + right\n",
    "\n",
    "        return left + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        depth = defaultdict(int)\n",
    "        fa = {}\n",
    "        def dfs(node, d, f):\n",
    "            if not node:\n",
    "                return \n",
    "            fa[node.val] = f\n",
    "            depth[node.val] = d\n",
    "            dfs(node.left, d + 1, node)\n",
    "            dfs(node.right, d + 1, node)\n",
    "\n",
    "        dfs(root, 0, None)\n",
    "\n",
    "        l, r = '', ''\n",
    "        s, d = startValue, destValue\n",
    "        while s != d:\n",
    "            if depth[s] >= depth[d]:\n",
    "                l += 'U'\n",
    "                s = fa[s].val\n",
    "            else:\n",
    "                nxt = fa[d]\n",
    "                if nxt.left and nxt.left.val == d:\n",
    "                    r += 'L'\n",
    "                else:\n",
    "                    r += 'R'\n",
    "                d = nxt.val\n",
    "        return l + r[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        s2r = {}\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return \"\"\n",
    "            if root.val == startValue:\n",
    "                s2r[root] = \"S\"\n",
    "                return \"S\"\n",
    "            # 深度遍历\n",
    "            from_left = dfs(root.left)\n",
    "            if len(from_left) >= 1:\n",
    "                s2r[root] = from_left + \"U\"\n",
    "                return s2r[root]\n",
    "            \n",
    "            from_right = dfs(root.right)\n",
    "            if len(from_right) >= 1:\n",
    "                s2r[root] = from_right + \"U\"\n",
    "                return s2r[root]\n",
    "            return \"\"\n",
    "        \n",
    "        dfs(root)\n",
    "        # for k, v in s2r.items():\n",
    "        #     print(k.val, v)\n",
    "        res = \"\"\n",
    "        def dfsd(root):\n",
    "            nonlocal res\n",
    "            if len(res) > 0:\n",
    "                return \"\"\n",
    "            if root is None:\n",
    "                return \"\"\n",
    "            if root.val == destValue:\n",
    "                if root in s2r and len(res) == 0:\n",
    "                    res = s2r[root] + \"D\"\n",
    "                return \"D\"\n",
    "            to_left = dfsd(root.left)\n",
    "            if len(to_left) > 0:\n",
    "                temp = \"L\" + to_left\n",
    "                if root in s2r and len(res) == 0:\n",
    "                    res = s2r[root] + temp\n",
    "                return temp\n",
    "            \n",
    "            to_right = dfsd(root.right)\n",
    "            if len(to_right) > 0:\n",
    "                temp = \"R\" + to_right\n",
    "                if root in s2r and len(res) == 0:\n",
    "                    res = s2r[root] + temp\n",
    "                return temp\n",
    "            return \"\"\n",
    "        \n",
    "        dfsd(root)\n",
    "        return res[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], s: int, d: int) -> str:\n",
    "        \n",
    "        flg = True\n",
    "        lca = -1\n",
    "        M = 10**5+1\n",
    "        p = [0]*M\n",
    "        lr = [0]*M\n",
    "        p[root.val]=-1\n",
    "        lr[root.val]=-1\n",
    "        # case if s is an of d \n",
    "        # d is an of s\n",
    "        # have a commen an \n",
    "        ctype = 2\n",
    "        level_s  = level_d = level_c = -1\n",
    "        def f(x, lv):\n",
    "            nonlocal flg , level_s, level_d, level_c, lca\n",
    "            rv = 0\n",
    "            if x.left:\n",
    "                rv |= f(x.left, lv+1)\n",
    "                p[x.left.val] = x.val\n",
    "                lr[x.left.val] = 1\n",
    "            if x.right:\n",
    "                rv |= f(x.right, lv+1)\n",
    "                p[x.right.val] = x.val\n",
    "            if flg and rv==3:\n",
    "                lca = x.val # or x.val\n",
    "                flg = False\n",
    "                level_c = lv\n",
    "                \n",
    "            if x.val == s:\n",
    "               \n",
    "                rv |= 1\n",
    "                level_s = lv\n",
    "               \n",
    "            if x.val == d:\n",
    "                rv |= 2\n",
    "                level_d = lv\n",
    "\n",
    "            if flg and rv == 3:\n",
    "                lca = x.val\n",
    "                flg = False\n",
    "                level_c = lv               \n",
    "                ctype = x.val == s # means start is up to dest\n",
    "            return rv\n",
    "        f(root, 0)\n",
    "        # print(lca, ctype)\n",
    "        if ctype == 0:\n",
    "            return \"U\"*(level_s - level_d)\n",
    "        else:            \n",
    "            x = []\n",
    "            if ctype == 2:\n",
    "                s = lca\n",
    "            while d!=s:\n",
    "                x.append(\"L\" if lr[d]==1 else \"R\")\n",
    "                d = p[d]\n",
    "            if ctype == 1:\n",
    "                return \"\".join(x)\n",
    "            else:\n",
    "                # print(level_s , level_c, level_d)\n",
    "                return \"U\"*(level_s - level_c) + \"\".join(reversed(x))\n",
    "\n",
    "        # hs = hd = -1\n",
    "        # p = [0] * (10 ** 5 + 1)\n",
    "        # lr = [0] * (10 ** 5 + 1)\n",
    "        # p[root.val] = -1\n",
    "\n",
    "        # def f(x, h):\n",
    "        #     nonlocal hs , hd\n",
    "        #     if x.val == s:\n",
    "        #         hs = h\n",
    "        #     if x.val == d:\n",
    "        #         hd = h\n",
    "        #     if x.left:\n",
    "        #         p[x.left.val] = x.val\n",
    "        #         lr[x.left.val] = 1\n",
    "        #         f(x.left, h + 1)\n",
    "        #     if x.right:\n",
    "        #         p[x.right.val] = x.val\n",
    "        #         f(x.right, h + 1)\n",
    "        # f(root, 0)\n",
    "\n",
    "        # xs, xd = s, d\n",
    "        # diff = hs - hd\n",
    "        # a = 0\n",
    "        # if  diff > 0:\n",
    "        #     while p[s]> 0 and diff:\n",
    "        #         s = p[s]\n",
    "        #         diff += 1\n",
    "        # b = []\n",
    "        # xy = ['R', 'L']\n",
    "        # if diff < 0:\n",
    "        #     while p[d] > 0 and diff < 0:\n",
    "        #         d = p[d]\n",
    "        #         diff -= 1\n",
    "        # while d != s:\n",
    "        #     d = p[d]\n",
    "        #     s = p[s]\n",
    "        # c = d\n",
    "        # s, d  = xs, xd\n",
    "        # a = 0\n",
    "        # while s!=c:\n",
    "        #     a+=1\n",
    "        #     s = p[s]\n",
    "        # while d!=c:\n",
    "        #     b.append(xy[lr[d]])\n",
    "        #     d = p[d]\n",
    "        \n",
    "        # return 'U' * a + ''.join(reversed(b))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def findPaths(root, direction, path, pathDict, level, nodes, flag, found1, found2, relation, levels):\n",
    "    if not root:\n",
    "        return\n",
    "\n",
    "    if root.val == nodes[0]:  #startValue\n",
    "        found1[0] = True\n",
    "        levels[0] = level\n",
    "        if found2[0]:\n",
    "            relation[0] = -1\n",
    "    elif root.val == nodes[1]:\n",
    "        levels[1] = level\n",
    "        found2[0] = True\n",
    "        if found1[0]:\n",
    "            relation[0] = 1\n",
    "\n",
    "    path[level] = (root.val, direction)\n",
    "    if nodes and root.val in nodes:\n",
    "        pathDict[root.val].extend(path[:level+1].copy())\n",
    "        # nodes.remove(root.val)\n",
    "\n",
    "    if found1[0] and found2[0]:\n",
    "        flag[0] = True\n",
    "        return\n",
    "\n",
    "    if root.left:\n",
    "        findPaths(root.left, 'L', path, pathDict, level+1, nodes, flag, found1, found2, relation, levels)\n",
    "        if flag[0]:\n",
    "            return\n",
    "\n",
    "    if root.right:\n",
    "        findPaths(root.right, 'R', path, pathDict, level+1, nodes, flag, found1, found2, relation, levels)\n",
    "\n",
    "\n",
    "    if root.val == nodes[0]:\n",
    "        found1[0]= False\n",
    "    elif root.val == nodes[1]:\n",
    "        found2[0] = False\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def getDirections(self, root, startValue, destValue):\n",
    "        \"\"\"\n",
    "        :type root: Optional[TreeNode]\n",
    "        :type startValue: int\n",
    "        :type destValue: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        nodes = [startValue, destValue]\n",
    "        pathDict = {startValue:[], destValue:[]}\n",
    "        path = [None] * 100000\n",
    "        flag = [False]\n",
    "        found1 = [False]\n",
    "        found2 = [False]\n",
    "        relation = [None]\n",
    "        levels = [-1,-1]\n",
    "\n",
    "        findPaths(root, None, path, pathDict, 0, nodes, flag, found1, found2, relation, levels)\n",
    "\n",
    "        # print(pathDict)\n",
    "\n",
    "        if relation[0] == 1: #起点是终点的祖先\n",
    "            # diff = levels[1] - levels[0]\n",
    "            startIdx = levels[0]+1\n",
    "            ans = ''\n",
    "            for x in pathDict[destValue][startIdx: ]:\n",
    "                ans += x[1]\n",
    "\n",
    "            return ans\n",
    "        elif relation[0] == -1: #终点是起点的祖先\n",
    "            diff = levels[0] - levels[1]\n",
    "            ans = 'U'*diff\n",
    "            return ans\n",
    "        else:\n",
    "\n",
    "            i = 0\n",
    "            while i < len(pathDict[startValue]) and i < len(pathDict[destValue]):\n",
    "                if pathDict[startValue][i][0] != pathDict[destValue][i][0]:\n",
    "                    parentId = i - 1\n",
    "                    break\n",
    "                i += 1\n",
    "\n",
    "            ans = 'U' * (len(pathDict[startValue]) - i )\n",
    "            for x in pathDict[destValue][parentId+1:]:\n",
    "                ans += x[1]\n",
    "            # parent = pathDict[destValue][parentId]\n",
    "            # for x in pathDict[destValue][parentId+1:]:\n",
    "            #     if x == parent.left:\n",
    "            #         ans += 'L'\n",
    "            #     else:\n",
    "            #         ans += 'U'\n",
    "\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        start = end = None\n",
    "        path = [[root.val, 'o']]\n",
    "        def dfs(x):\n",
    "            nonlocal start, end\n",
    "            if start and end:\n",
    "                return\n",
    "            if x.val == startValue:\n",
    "                start = deepcopy(path)\n",
    "            if x.val == destValue:\n",
    "                end = deepcopy(path)\n",
    "            if x.left:\n",
    "                path.append([x.left.val, 'L'])\n",
    "                dfs(x.left)\n",
    "                path.pop()\n",
    "            if x.right:\n",
    "                path.append([x.right.val, 'R'])\n",
    "                dfs(x.right)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(root)\n",
    "        i, m = 0, min(len(start), len(end))\n",
    "        while i < m and start[i] == end[i]:\n",
    "            i += 1\n",
    "        return 'U'*(len(start)-i) + ''.join(end[j][1] for j in range(i,len(end)))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        graph = defaultdict(list)\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.left:\n",
    "                graph[node.val].append((node.left.val, \"L\"))\n",
    "                graph[node.left.val].append((node.val, \"U\"))\n",
    "            if node.right:\n",
    "                graph[node.val].append((node.right.val, \"R\"))\n",
    "                graph[node.right.val].append((node.val, \"U\"))\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "        helper(root)\n",
    "        q = deque()\n",
    "        q.append((startValue, \"\"))\n",
    "        visited = set()\n",
    "        \n",
    "        while q:\n",
    "            node, path = q.popleft()\n",
    "            if node == destValue:\n",
    "                return path\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "            for neighbor, direction in graph[node]:\n",
    "                q.append((neighbor, path+direction))\n",
    "        return \"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left:\n",
    "                v, lv = node.val, node.left.val\n",
    "                g[v].append((\"L\", lv))\n",
    "                g[lv].append((\"U\", v))\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                v, rv = node.val, node.right.val\n",
    "                g[v].append(('R', rv))\n",
    "                g[rv].append((\"U\", v))\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        vis = set()\n",
    "        vis.add(startValue)\n",
    "\n",
    "        # q中放start的临近节点\n",
    "        q = deque([y for y in g[startValue]])\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if x[1] == destValue:\n",
    "                return x[0]\n",
    "                \n",
    "            for y in g[x[1]]:\n",
    "                if not y[1] in vis:\n",
    "                    q.append((x[0] + y[0], y[1]))\n",
    "                    vis.add(y[1])\n",
    "        \n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
